#define _CRT_SECURE_NO_WARNINGS 1




///https://www.luogu.com.cn/problem/P1616





//#include<iostream>
//using namespace std;
//const int N = 1e4 + 10, M = 1e7 + 10;
//typedef long long LL;
//int n, m;
//int t[N], w[N];
//LL dp[M];
//int main()
//{
//	cin >> m >> n;
//	for (int i = 1;i <= n;i++)
//		cin >> t[i] >> w[i];
//
//	for (int i = 1;i <= n;i++)
//	{
//		for (int j = t[i];j <= m;j++)
//		{
//			dp[j] = max(dp[j], dp[j - t[i]] + w[i]);
//		}
//	}
//
//	cout << dp[m];
//	return 0;
//}